A viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoding is used in decoding a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a system that is transmitted through various media with each set of bits representing a symbol instant. Viterbi decoding is employed in digital communications over any communication channel, such as satellite-to-earth, cellular telephony, computer-to-disk, modem-to-modem and others. Viterbi decoders have been implemented on hardware having a single multiply-accumulate (MAC) capability such as single MAC microprocessors, microcontrollers, or digital signal processors. Viterbi decoding is well known and applications can be found in U.S. Pat. Nos. 5,490,178; 5,454,014; 5,559,837; 5,465,275; and 5,471,500, the disclosures of which are hereby incorporated by reference.
A viterbi implementation consists of four steps: (1) branch and path metric computation; (2) a compare-select operation; (3) a minimum or maximum state cost determination; and (4) a traceback operation. In the decoding process, a viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which one-bit sequence was most likely to have been transmitted. The possible transitions from a state at one symbol instant or state to a state at a next, subsequent symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can only transition to a limited number of next states upon receipt of the next bit or bits in the bit stream. Thus, some paths survive and other paths do not survive during the decoding process. By eliminating those transitions that are not permissible, computational efficiency can be achieved in determining the most likely paths to survive. The viterbi decoder typically defines and calculates a branch metric associated with each branch and employs the branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric or accumulated cost that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as an extremum of the sum of the branch metric for the possible transitions and the path accumulated cost at the previous state. Either the maximum or minimum extremum may be selected.
While several paths survive the transition from one symbol instant to the next symbol instant, a traceback operation through the possible branches is employed to select the most likely bit or bit sequence to have been transmitted. Representing the sequential symbol instants in an array is referred to as a trellis. Identifying the extremum accumulated cost path starting with a given symbol instant is referred to as a traceback operation. The number of symbol instants back through the trellis that the extremum accumulated cost path extends is the length, or depth, of the traceback operation. The individual state in the trellis associated with the extremum accumulated cost at the end of the traceback operation is translated into the most likely bit or bits to have been transmitted in that symbol instant. The bit or group of bits is referred to as a decoded symbol.
Historically viterbi decoders have been implemented on hardware having a single MAC capability which limits the efficiency that can be achieved in digital processing of the transmitted signal. What is needed is a multiple MAC capability to provide a more efficient implementation of a viterbi decoder.